package com.summli.basic.class07;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的序列化和反序列化
 */
public class Code04_SerializeAndReconstructTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    // 先序序列化
    public static Queue<String> preSerial(Node head) {
        Queue<String> queue = new LinkedList<>();
        pre(head,queue);
        return queue;
    }

    private static void pre(Node head, Queue<String> queue) {
        if(head == null){
            queue.add(null);
        }else{
            queue.add(String.valueOf(head.value));
            pre(head.left, queue);
            pre(head.right, queue);
        }
    }

    // 先序反序列化
    public static Node buildByPreQueue(Queue<String> prelist) {
        if(prelist == null || prelist.size() == 0){
            return null;
        }
        return preb(prelist);
    }

    private static Node preb(Queue<String> prelist) {
        String value = prelist.poll();
        if(value == null){
            return null;
        }
        Node head = new Node(Integer.parseInt(value));
        head.left=preb(prelist);
        head.right=preb(prelist);
        return head;
    }


    // 广度优先遍历的序列化和反序列化
    // 使用两个队列，一个记录二叉数的节点，一个记录结果值
    // 如果为null进入结果队列，不进入help队列，否则都进
    public static Queue<String> levelSerial(Node head) {
        Queue<String> result = new LinkedList<>();
        if(head == null){
            result.add(null);
        }else{
            Queue<Node> help = new LinkedList<>();
            help.add(head);
            result.add(String.valueOf(head.value));
            while(!help.isEmpty()){
                Node poll = help.poll();
                if(poll.left != null){
                    help.add(poll.left);
                    result.add(String.valueOf(poll.left.value));
                }else{
                    result.add(null);
                }
                if(poll.right != null){
                    help.add(poll.right);
                    result.add(String.valueOf(poll.right.value));
                }else{
                    result.add(null);
                }
            }
        }
        return result;
    }

    public static Node buildByLevelQueue(Queue<String> levelList) {
        if(levelList == null || levelList.size() == 0){
            return null;
        }
        Queue<Node> help = new LinkedList<Node>();
        Node head = generateNode(levelList.poll());
        if(head != null){
            help.add(head);
        }
        while(!help.isEmpty()){
            Node poll = help.poll();
            poll.left = generateNode(levelList.poll());
            poll.right = generateNode(levelList.poll());
            if(poll.left != null){
                help.add(poll.left);
            }
            if(poll.right != null){
                help.add(poll.right);
            }
        }
        return head;
    }

    private static Node generateNode(String poll) {
        if(poll == null){
            return null;
        }
        return new Node(Integer.parseInt(poll));
    }


    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    // for test
    public static boolean isSameValueStructure(Node head1, Node head2) {
        if (head1 == null && head2 != null) {
            return false;
        }
        if (head1 != null && head2 == null) {
            return false;
        }
        if (head1 == null && head2 == null) {
            return true;
        }
        if (head1.value != head2.value) {
            return false;
        }
        return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
    }
    public static void printNode(Node head){
        if(head == null){
            return;
        }
        System.out.print(head.value+"   ");
        printNode(head.left);
        printNode(head.right);
    }
    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            Queue<String> pre = preSerial(head);
            Queue<String> level = levelSerial(head);
            Node preBuild = buildByPreQueue(pre);
            Node levelBuild = buildByLevelQueue(level);
            if (!isSameValueStructure(preBuild, levelBuild)) {
                System.out.println();
                System.out.println("pre:");
                printNode(preBuild);
                System.out.println();
                System.out.println("level:");
                printNode(levelBuild);
                System.out.println();
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("finish!");
    }
}
